package _11_整理题目._4_动态规划._硬币找零;

import org.junit.Test;

import java.util.Arrays;

/**
 * 给定不同面额的硬币 coins 和一个总金额 amount。
 * 编写一个函数来计算可以凑成总金额所需的最少的硬币个数。
 * 如果没有任何一种硬币组合能组成总金额，返回 -1。
 * 你可以认为每种硬币的数量是无限的
 *
 * 动态规划模板：
 * 1、定义 dp[] 中 dp[i] 的意思，初始化 dp 长度
 *      dp[n] 定义：输入金额 n 时，最少的硬币数目
 * 2、确定边界值，即最初值 dp[0] = 0; dp[<0] = -1;
 * 3、确定状态转移方程，即 dp[i] 和 dp[i-1] 的关系
 *      dp[i] = Math.min(dp[i-coin]+1)   for(int coin : coins)
 * 
 */
public class _01_最少硬币数目 {
    
    public int coinChange(int[] coins, int amount) {
        if(amount<0) return -1;
        int[] dp = new int[amount+1];
        Arrays.fill(dp, amount+1);
        dp[0] = 0;
        for(int i=1; i<amount+1; i++) {
            for(int coin : coins) {
                if(i-coin < 0) continue;
                dp[i] = Math.min(dp[i], dp[i-coin]+1);
            }
        }
        System.out.println(Arrays.toString(dp));
        if(dp[amount]==amount+1) {
            return -1;
        } else {
            return dp[amount];
        }
    }
    
    @Test
    public void main() {
        int[] coins = {1, 2, 5};
        System.out.println(coinChange(coins, 12));
        assert coinChange(coins, 33) == 8;
    }
    
}
